'''
Created on 14.11.2012

@author: felix_000
'''
from game import GameLogic
import copy
from game.datastructure.PentalathField import PentalathField
from game.datastructure.PlayerColor import PlayerColor
import math
from game.player.alpha_beta_player.alpha_beta_framework.moveordering.MoveOrdering import MoveOrdering
from game.player.alpha_beta_player.alpha_beta_framework.movefilter.NoEmptySpaceMovesFilter import NoEmptySpaceMovesFilter
from timeit import Timer
import functools
import time


INF = 12345678
MINF = -INF
        
def isTerminalNode(node):
    field, action = node
    return action is not None and GameLogic.won(field, action)





class ChildIter:
    def __init__(self, field, color, actions):
        self.field = field
        self.color = color
        self.started = False
        self.swapped = False
        self.actions = actions
    
    @classmethod
    def constructActions(cls, field, color):
        start = time.time()
        actions = GameLogic.getAllowedFields(field, color)
#        moveOrdering = MoveOrdering()
        #moveFilter = NoEmptySpaceMovesFilter()
        #moveFilter.filter(field, actions)
        #moveOrdering.order(field, actions, color)
#        if switchAllowed:
#            actions.insert(0, GameLogic.SWAP_ACTION)
        return cls(field, color, actions)
        
    
    def __iter__(self):
        return self
    
    def undo(self):
        self.field.undo(len(self.field.history)-self.historyLen)
    
    def next(self):
        if len(self.actions) == 0:
            if self.started:
                self.undo()
                self.started = False
            raise StopIteration
        action = self.actions.pop(0)
        if self.started:
            self.undo()
        else:
            self.started = True
        if action == -1:
            self.swapped = True
            action = self.field.history[0]
        elif self.swapped:
            self.swapped = False
        self.historyLen = len(self.field.history)
        x,y = action            
        self.field.place(self.color, x, y)
        GameLogic.applyAction(self.field, action, self.color)
        return (self.field, (x,y))
    
    def close(self):
        if self.started:
            self.undo()
            self.started = False


def childs(node, color):
    ofield = node[0]
    actions = GameLogic.getAllowedFields(ofield, color)
    childs = []
    for action in actions:
        field = copy.deepcopy(ofield)
        x,y = action
        field.place(color, x, y)
        childs.append((field, action))
    return childs

class NegaMax:
    def __init__(self, heuristicFeatures, moveFilter, depth):
        self.heuristicFeatures = heuristicFeatures
        self.startDepth = depth
        self.killerMoves = [None for i in xrange(60) ]
        self.killerMovePly = 0
        self.moveFilter = moveFilter
        
    def outOfTime(self):
        # if no time is left for searching
        return self.stopEvent.is_set()
        
    def heuristic(self, node, color, depth):
        field, action = node
        rating = 0
        for heuristicFeature in self.heuristicFeatures:
            rating += heuristicFeature.heuristic(field, action, color, color, depth) * heuristicFeature.weighting
        return -rating
    
    def adjustKillerMoves(self):
        # one depth can be deleted, rest should be shifted down
        self.killerMoves[:] = [self.killerMoves[i] if i > 1 else None for i in xrange(len(self.killerMoves)) ]
    
    def search(self, field, color, switchAllowed, ply, stopEvent):
        # adjust killermove (depths are all shifted down)
        self.stopEvent = stopEvent
        if ply != self.killerMovePly:
            self.adjustKillerMoves()
        self.killerMovePly = ply
        self.startColor = color
        self.switchAllowed = switchAllowed
        
        self.abc = 0
        self.pruned = 0
        self.stop = 0
        #maxVal = self.negamax((field, None), self.startDepth, float("-inf"), float("inf"), color)
        #maxVal = self.principalVariationSerach((field, None), float("-inf"), float("inf"), 3, color)
        maxVal = self.iterativeDeepening(field, color, 200)
        print "Called", self.abc
        print "Pruned", self.pruned
        print "Stopped", self.stop
        print "Found ", maxVal, " => ", self.action
        return self.action
        
    def saveAction(self, node, value):
        self.action = node[1]
        
    def addKillerMove(self, childs, killerMove, node, color):
        field = node[0]
        if GameLogic.isAllowed(field, killerMove, color):
            if killerMove in childs.actions:
                childs.actions.remove(killerMove)
            childs.actions.insert(0, killerMove)
    
    def iterativeDeepening(self, field, color, maxDepth):
        actions = [[action, 0] for action in GameLogic.getAllowedFields(field, color)]
        for depth in xrange(0,maxDepth+1, 1):
            #self.killerMoves = [None for i in range(depth) ]
            if self.outOfTime():
                break
            print "Depth", depth
            bestMoveValue = MINF
            childs = ChildIter(field, color, [action[0] for action in actions])
            av = 0
#            firstIt = True
            self.abc = 0
            self.pruned = 0
            self.stop = 0
            for child in childs:
                action, value = actions[av]
                self.startDepth = depth
                value = -self.negamax(child, depth, bestMoveValue, INF, -color)
                if self.outOfTime():
                    break
#                if firstIt:
#                    firstIt = False
#                    for i in xrange(len(actions)):
#                        actions[i][1] = MINF
                actions[av] = [action, value]
                if value > bestMoveValue:
                    bestMoveValue = value
                av += 1
            childs.close()
            
            print "Called", self.abc
            print "Pruned", self.pruned
            print "Stopped", self.stop
            actions.sort(key=lambda avp : -avp[1])
            print actions
        self.action = actions[0][0]
        return actions[0][1]
            
        
    
    def negamax(self, node, depth, alpha, beta, color):
        self.abc += 1
        if self.outOfTime():
            return MINF
        if depth <= 0 or isTerminalNode(node):
#            start = time.time()
#            for i in range(10000):
#                self.heuristic(node, -color, depth)
#            print (time.time()-start)/10000.
            return self.heuristic(node, -color, depth)
        if (node[1] is not None) and (not self.moveFilter.acceptable(node[0], node[1])):
            return INF
        realDepth = self.startDepth-depth
        tryKillerMove = (self.killerMoves[realDepth] is not None)
        maxVal = MINF
        childs = ChildIter.constructActions(node[0], color)
        if tryKillerMove:
            # places killer move at the first position
            self.addKillerMove(childs, self.killerMoves[realDepth], node, color)
        for child in childs:
            
            value = -self.negamax(child, depth-1, -beta, -maxVal, -color)
            if value > maxVal:
                maxVal = value
#                if depth == self.startDepth:
#                    self.saveAction(child, value)
            if maxVal > alpha:
                alpha = maxVal
            if maxVal >= beta:
                self.killerMoves[realDepth] = child[1]
                self.pruned += 1
                break
        childs.close()
        return maxVal
    
    def principalVariationSerach(self, node, alpha, beta, depth, color):
        print "PVS", depth
        if depth <= 0 or isTerminalNode(node):
            return self.heuristic(node, color, depth)
        childIter = ChildIter.constructActions(node[0], color, False)
        nextN = childIter.next()
        best = -self.principalVariationSerach(nextN, -beta, -alpha, depth-1, -color)
        self.saveAction(nextN, best)
        nextN = childIter.next()
        
        for nextN in childIter:
            if best >= beta:
                break;
            lower = max((alpha, best))
            merit = -self.ZWS(nextN, -lower, depth-1, True, -color)
            if merit > lower:
                merit = -self.principalVariationSerach(nextN, -beta, -merit, depth-1, -color)
            if merit > best:
                best = merit
                if depth == self.startDepth:
                    self.saveAction(nextN, merit)
        childIter.close()
        return best
    
    #def reduceSearch(self, ):
    
    def ZWS(self, node, bound, depth, tryNullMove, color):
        print "ZWS", depth
        EPSILON_ZWS = 10
        if depth == 0 or isTerminalNode(node):
            return self.heuristic(node, color, depth)
        childIter = ChildIter.constructActions(node[0], color, False)
        nextN = childIter.next()
#        r = reduceSearch(nextN, depth)
#        if forwardPrune(nextN, tryNullMove, depth > r):
#            # Null move
#            merit = -self.ZWS(node, -bound+EPSILON_ZWS, depth-1-r, False, -color)
#            if merit >= bound:
#                return bound
        childIter = ChildIter.constructActions(node[0], color, False)
        estimate = MINF
        for nextN in childIter:
            merit = -self.ZWS(nextN, -bound+EPSILON_ZWS, depth-1, True, -color)
            if merit > estimate:
                estimate = merit
                if estimate >= bound:
                    break;
        childIter.close()
        return estimate